/**
 * 
 */
package dp.passed2;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
import java.util.List;

/**
 * @author michael
 *
 */
public class WordBreak {

	/*
	Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
	
	For example, given
	s = "leetcode",
	dict = ["leet", "code"].
	
	Return true because "leetcode" can be segmented as "leet code".
	 */
    public boolean wordBreak1(String s, Set<String> dict) {
        boolean[] breakable = new boolean[s.length() + 1];
        breakable[0] = true;
        for (int i = 1, size = s.length(); i <= size; i++) {
            for (int j = i; j >= 0; j--) {
                if (breakable[j] && dict.contains(s.substring(j, i))) {
                    breakable[i] = true;
                }
            }
        }
        
        return breakable[s.length()];
    }
    
    /*
	 Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
	
	Return all such possible sentences.
	
	For example, given
	s = "catsanddog",
	dict = ["cat", "cats", "and", "sand", "dog"].
	
	A solution is ["cats and dog", "cat sand dog"].
     */
    public List<String> wordBreak2R(String s, Set<String> dict) {
    	Map<String, List<String>> cache = new HashMap<>();
     
    	return wordBreak2RHelper(s, dict, cache);
    }
	
    public List<String> wordBreak2RHelper(String s, Set<String> dict, Map<String, List<String>> cache) {
        if (cache.containsKey(s)) return cache.get(s);
        
        List<String> sentences = new LinkedList<>();
        if (dict.contains(s)) {
        	sentences.add(s);
        }
        for (int i = 1, size = s.length(); i < size; i++) {
        	String prefix = s.substring(0, i);
        	if (dict.contains(prefix)) {
        		String suffix = s.substring(i);
        		List<String>suffixSentences = wordBreak2RHelper(suffix, dict, cache);
        		for (String sentence : suffixSentences) {
        			sentences.add(prefix.concat(" ").concat(sentence));
        		}
        	}
        }
    	cache.put(s, sentences);
    	return sentences;
    }
    
    //Slight improved
//    private final Map<String, List<String>> cache = new HashMap<>();
//
//    private boolean containsSuffix(Set<String> dict, String str) {
//        for (int i = 0; i < str.length(); i++) {
//            if (dict.contains(str.substring(i))) return true;
//        }
//        return false;
//    }
//
//    public List<String> wordBreak(String s, Set<String> dict) {
//        if (cache.containsKey(s)) return cache.get(s);
//        List<String> result = new LinkedList<>();
//        if (dict.contains(s)) result.add(s);
//        for (int i = 1; i < s.length(); i++) {
//            String left = s.substring(0,i), right = s.substring(i);
//            if (dict.contains(left) && containsSuffix(dict, right)) {
//                for (String ss : wordBreak(right, dict)) {
//                    result.add(left + " " + ss);
//                }
//            }
//        }
//        cache.put(s, result);
//        return result;
//    }
    
    
    
//    public boolean wordBreak3R(String s, Set<String> dict) {
//    }
//    
//    public boolean wordBreak3RHelper(String s, Set<String> dict, Map<>) {
//    }
    
    
	/**
	 * 
	 */
	public WordBreak() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
